package cn.com.guage.dtm.jubian;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
/**
 * 这段 Java 代码的主要功能是解决一个路径规划相关的问题，具体来说是计算从原点 (0, 0) 出发，
 * 依次经过给定的多个点，最后再回到原点的所有可能路径的总距离，并找出其中的最短距离。
 * 此代码旨在解决一个路径规划问题，具体是计算从原点 (0, 0) 出发，依次经过给定的多个点，最后再回到原点的所有可能路径的总距离，
 * 进而找出其中的最短距离。为达成这一目标，代码主要运用了全排列算法和欧几里得距离算法。
 */

/**
 * 实现步骤
 * 标记数组：flags 数组用来标记每个点是否已经在当前路径中被使用。
 * 递归终止条件：当 flags 数组中的所有元素都为 true 时，意味着已经生成了一个完整的路径排列，此时将其添加到 list 中。
 * 递归调用：针对每个未被使用的点，将其标记为已使用，添加到当前路径中，然后递归调用 getOne 方法生成剩余点的排列。
 * 回溯操作：递归返回后，把该点标记为未使用，以便尝试其他可能性。
 */

public class 蜜蜂采蜜_最短路径 {

    //用于存储所有可能的路径排列，每个路径排列是一个字符串数组，数组中的元素代表点的名称。
    static ArrayList<String[]> list = new ArrayList();
    //用于存储每个点的名称及其对应的坐标，键是点的名称，值是一个包含 x 和 y 坐标的整数数组。
    static HashMap<String, int[]> hashMap;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        //200 0 200 10 200 50 200 30 200 25
        String[] numbers = {"A", "B", "C", "D", "E"};
        Scanner sc = new Scanner(System.in);
        List<int[]> listInputTerm = new ArrayList<int[]>();
        String inLine =  sc.nextLine();
        String [] array = inLine.split(" ");
        for (int i = 0; i < array.length; i=i+2) {
            int[] a = new int[2];
            a[0] = Integer.parseInt(array[i]);
            a[1] = Integer.parseInt(array[i+1]);
            listInputTerm.add(a);
        }

        hashMap = new HashMap<>();

        hashMap.put("A", listInputTerm.get(0));
        hashMap.put("B", listInputTerm.get(1));
        hashMap.put("C", listInputTerm.get(2));
        hashMap.put("D", listInputTerm.get(3));
        hashMap.put("E", listInputTerm.get(4));

        getOne(new boolean[numbers.length], numbers, "");
        for (String[] strings : list) {
            // System.out.println(Arrays.toString(strings) + "=" + (int) getInstance(strings));
            if ((int) getInstance(strings)<min){
                min=(int) getInstance(strings);
            }
        }
        System.out.println(min);

    }
    //调用 getOne 方法生成所有可能的路径排列，并将结果存储在 list 中

    /**
     * 全排列算法：getOne 方法使用递归回溯的方式生成所有可能的路径排列。通过标记数组 flags 来确保每个点只被使用一次，
     * 每次递归调用时更新标记数组，递归返回后恢复标记，从而生成所有可能的排列。
     * @param flags
     * @param numbers
     * @param numStr
     */
    /**
     * 生成所有路径排列：调用 getOne 方法生成所有可能的路径排列，并将结果存储在 list 中。
     * @param flags
     * @param numbers
     * @param numStr
     */
    public static void getOne(boolean[] flags, String[] numbers, String numStr) {

        boolean print = true;
        for (int i = 0; i < numbers.length; i++) {
            print = print && flags[i];
        }
        if (print) {
            String s = numStr.substring(0, numStr.length() - 1);
            String[] split = s.split(",");
            //System.out.println(Arrays.toString(split));
            list.add(split);
            return;
        }
        for (int i = 0; i < numbers.length; i++) {
            if (!flags[i]) {
                flags[i] = true;
                getOne(flags, numbers, numStr + numbers[i] + ",");
                flags[i] = false;
            }

        }
        System.out.println(list);
    }

    /**
     * 欧几里得距离算法：getInstance(int x1, int y1, int x2, int y2) 方法使用欧几里得距离公式
     * @param strings
     * @return
     */
    public static double getInstance(String[] strings) {
        double sum = 0;
        int x = 0;
        int y = 0;
        for (int i = 0; i < strings.length; i++) {
            int[] ints = hashMap.get(strings[i]);
            if (ints != null) {
                sum += getInstance(x, y, ints[0], ints[1]);
                x = ints[0];
                y = ints[1];
            }
        }
        sum = sum + getInstance(x, y, 0, 0);
        return sum;
    }

    public static double getInstance(int x1, int y1, int x2, int y2) {
        //欧几里得距离算法用于计算两点之间的直线距离。在该问题中，利用此算法来计算路径中相邻两点之间的距离，进而计算整个路径的总距离。
        //距离公式：使用欧几里得距离公式 d = sqrt((x1 - x2)^2 + (y1 - y2)^2) 来计算两点之间的距离。
        double result = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
        return result;
    }
}
